package com.zhang.topic;

import java.util.HashMap;

/**
 * @title: 爬楼梯
 * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
 * @author: zhang
 * @date: 2022/4/5 21:26
 *
 * 斐波那契数列于此解法相同
 * f(0)=0 n=0;
 * f(1)=1 n=1;
 * f(n)=f(n-2)+f(n-1) n>1
 */
public class LeetCode70 {
    public static void main(String[] args) {
        System.out.println(Method2(20));
    }


    private static HashMap<Integer, Integer> storeMap = new HashMap<>();
    public static int Method1(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        if (storeMap.get(n) != null){
            return storeMap.get(n);
        }else {
            int result = Method1(n-1)+Method1(n-2);
            storeMap.put(n,result);
            return result;
        }
    }


    /**动态规划*/
    public static int Method2(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        int result = 0;
        int pre = 2;
        int prePre = 1;
        for (int i = 3; i <= n ; i++) {
            result = pre + prePre;
            prePre = pre;
            pre = result;
        }
        return result;
    }

}
